package com.gary;

/**
 * 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,1]
 * 输出：true
 *
 * 示例 2：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：false
 *
 * 示例 3：
 *
 * 输入：nums = [1,1,1,3,3,4,3,2,4,2]
 * 输出：true
 *
 *
 * 方法一： hash表
 * 方法二： 暴力搜索
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author peng_rui
 * @date 2022/3/3
 */
public class ContainsDuplicate {
    public static void main(String[] args) {
        int[] nums = new int[]{-136,-919,971,369,-841,566,143,174,617,793,676,-357,-303,424,-282,218,18,188};
        boolean result = containsDuplicate(nums);
        System.out.println(result);

    }
    public static boolean containsDuplicate(int[] nums) {
        int size = nums.length ;
        //长度为一直接返回
        if (size <= 1) {
            return false;
        }
        //hash表
        int[] hashArray = new int[size];
        //记0操作
        int count0 = 0;
        for (int i = 0; i < size; i++) {

            if (nums[i] == 0) {
                count0++;
                if (count0 > 1) {
                    return true;
                }
                continue;
            }
            //计算hashCode
            int hashCode = nums[i]  % size;
            if (hashCode < 0) {
                hashCode += size;
            }
            while (true) {
                if (hashArray[hashCode] == 0) {
                    hashArray[hashCode] = nums[i];
                    break;
                } else if (hashArray[hashCode] == nums[i]) {
                        return true;
                } else {
                    hashCode++;
                    if (hashCode >= size) {
                        hashCode -= size;
                    }
                }
            }

        }
        return false;
    }
}
